OJ每日练习（11）

Posted on | In

（今天被JSON解析器的bug拖住了，OJ只刷剑指offer）

题目名称

  1. 序列化二叉树（剑指offer #37）
  2. 数组中出现超过一半的数字（剑指offer #39）
  3. 最小的k个数（剑指offer #40)
  4. 数据流的中位数（剑指offer #41)
  5. 连续子数组的最大和（剑指offer #42)
  6. 1~n整数中1出现的次数（剑指offer #43）

序列化二叉树（剑指offer #37）

解题思路

前序遍历，遇到根节点后将其转为字符。接着处理左右子树。反序列化则解析出节点后作为根，然后递归解析左右子树。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(!root)
            return nullptr;
        string str;
        aux_s(root,str);
        char* res = new char[str.length()+1];
        strcpy(res,str.c_str());
        return res;
    }
    TreeNode* Deserialize(char* str){
        if(!str)
            return nullptr;
        TreeNode* res = aux_d(str);
        return res;
    }
private:
    void aux_s(TreeNode* root,string& str){
        if(!root){
            str+='#';
            return;
        }
        string r = to_string(root->val);
        str+=r;
        str+=',';
        aux_s(root->left,str);
        aux_s(root->right,str);
    }
    TreeNode* aux_d(char* &str){
        if(*str=='#'){
            ++str;
            return nullptr;
        }
        int num=0;
        while(*str!='\0' && *str!=','){
            num=num*10+(*str-'0');
            ++str;
        }
        TreeNode* root = new TreeNode(num);
        if(*str=='\0')
            return root;
        else
            ++str;
        root->left=aux_d(str);
        root->right=aux_d(str);
        return root;     
    }
};

数组中超过一半的数字

解题思路

排序后超过一半的数字必然是中位数，我们只需要判断中位数出现的次数是否大于一半即可，但这需要O（nlogn）。不妨采取攻防策略：初始化count为0，遇到一个数后将它认为是目标值。若后续出现了不同的则减1，相同的则加1.若count==0，将则认为目标值是下一个元素，并再将其置1.最后判定目标值是否正确。只需要两次遍历，时间为O（n)。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
       if(numbers.empty())
           return 0;
       int res=numbers[0];
       int count=1;
       for(int i=1;i!=numbers.size();++i){
           if(numbers[i]==res) ++count;
           else --count;
           if(count==0){
               res=numbers[i];
               count=1;
           }
       }
       count=0;
       for(auto i:numbers)
           if(i==res) ++count;
       if(count>numbers.size()/2)
           return res;
       else
           return 0;
    }
};

最小的k个数

解题思路

考察STL中partial_sort的实现，采用大顶堆即可。值得注意的是对于heap_algo需要熟练，先pop_heap再pop_back。进入时先push_back再push_heap。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> a, int k) {
        if(a.empty() || k>a.size() || k<=0)
            return vector<int>();
        vector<int> res(a.cbegin(),a.cbegin()+k);
        make_heap(res.begin(),res.end());
        for(int i=k;i!=a.size();++i){
            if(a[i]<res[0]){
                pop_heap(res.begin(),res.end());
                res.pop_back();
                res.push_back(a[i]);
                push_heap(res.begin(),res.end());
            }
        }
        sort_heap(res.begin(),res.end());
        return res;
    }
};

数据流中位数

解题思路

这道题有点类似于之前做的两个数组的中位数，但有所不同。这道题的核心思想在于使用一个大顶堆和一个小顶堆，保证大堆中的元素比小堆中的元素都要小，则中位数必然在两个堆顶元素中。在执行插入操作时，仅在当前元素小于大顶堆首或大顶堆为空时插入大顶堆，否则默认插入小顶堆。若大顶堆元素个数超出小顶堆两个，将其top push进入小顶堆。若小顶堆元素超过大顶堆一个，则将其top push进入大顶堆。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void Insert(int num){
        if(p.empty()||num<p.top()) p.push(num);
        else q.push(num);
        if(p.size()==q.size()+2) q.push(p.top()),p.pop();
        if(p.size()+1==q.size()) p.push(q.top()),q.pop();
    }

    double GetMedian(){ 
        return p.size()==q.size()?(p.top()+q.top())/2.0:p.top();
    }
private:
    priority_queue<int,vector<int>,less<int> >p;
    priority_queue<int,vector<int>,greater<int> >q;
};

最大的连续子序列和

解题思路

一维动态规划,f代表当前连续序列和。

解题方案

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res=INT_MIN,f=0;
        for(int i=0;i<nums.size();++i)
            f=max(f+nums[i],nums[i]),res=max(res,f);
        return res;
    }
};

1~n整数中1出现的次数

解题思路

根据数位判断个数，具体的思路可见 https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6 大牛咩咩提出的方案。（核心就是判断i这一位是大于等于2，还是等于1）

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n){
        int count=0;
        for(long long i=1;i<=n;i*=10){
            int a=n/i,b=n%i;
            count += (a+8)/10*i+(a%10==1)*(b+1);
        }
        return count;
    }
};